package problems.contest;

import utils.beans.TreeNode;

import java.util.*;

/**
 * <p>https://leetcode.cn/contest/weekly-contest-306/</p>
 *
 * @author habitplus
 * @since 2022/8/21 9:06
 */
public class WCT306 {
    /**
     * T1：模拟
     */
    public int minNumberOfHours(int initialEnergy, int initialExperience, int[] energy, int[] experience) {

        int eSum = 0;
        for (int e : energy) eSum += e;

        int ex = 0;
        for (int e : experience) {
            if (initialExperience > e) {
                initialExperience += e;
            } else {
                ex += (e - initialExperience + 1);
                initialExperience = 2 * e + 1;
            }
        }

        int en = initialEnergy > eSum ? 0 : eSum + 1 - initialEnergy;
        return en + ex;
    }

    /**
     * T2：HASH计数
     */
    public String largestPalindromic(String num) {
        char[] chs = num.toCharArray();
        int[] m = new int[10];

        for (char c : chs) ++m[c - '0'];

        StringBuilder sb = new StringBuilder();
        boolean isFirst = true;
        int k;
        while ((k = findTwo(m, !isFirst)) != -1) {
            isFirst = false;
            sb.append(k);
        }

        String s1 = sb.toString();
        String s2 = sb.reverse().toString();
        int single = -1;
        for (int i = m.length - 1; i >= 0; --i) {
            if (m[i] > 0) {
                single = i;
                break;
            }
        }

        return single != -1 ? s1 + single + s2 : s1 + s2;
    }
    private int findTwo(int[] m, boolean zero) {

        for (int i = m.length - 1; i > 0; --i) {
            if (m[i] > 1) {
                m[i] -= 2;
                return i;
            }
        }

        if (zero && m[0] > 1) {
            m[0] -= 2;
            return 0;
        }

        return -1;
    }

    /**
     * T3：BFS
     */
    public int amountOfTime(TreeNode root, int start) {
        if (root == null) return 0;
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        TreeNode node;
        int k, r;
        while (!que.isEmpty()) {
            for (int i = que.size(); i > 0; --i) {
                node = que.poll();
                List<Integer> list = map.getOrDefault(node.val, new ArrayList<>());
                if (node.left != null) {
                    k = node.left.val;
                    list.add(k);
                    List<Integer> tmpList = map.getOrDefault(k, new ArrayList<>());
                    tmpList.add(node.val);
                    map.put(k, tmpList);
                    que.add(node.left);
                }
                if (node.right != null) {
                    k = node.right.val;
                    list.add(k);
                    List<Integer> tmpList = map.getOrDefault(k, new ArrayList<>());
                    tmpList.add(node.val);
                    map.put(k, tmpList);
                    que.add(node.right);
                }
                map.put(node.val, list);
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        HashSet<Integer> set = new HashSet<>();
        List<Integer> list;
        queue.offer(start);
        set.add(start);
        int ret = -1;
        while (!queue.isEmpty()) {
            for (int i = queue.size(); i > 0; --i) {
                k = queue.poll();
                list = map.get(k);
                if (list != null) {
                    for (int e : list) {
                        if (!set.contains(e)) {
                            queue.offer(e);
                            set.add(e);
                        }
                    }
                }

            }
            ++ret;
        }

        return ret;
    }
}
